#p590

from collections import deque as Queue

class node:
    def __init__(self,i,x):
        self.id = i
        self.successors=[]
        self.successors.extend(x)

n1=node(1,[2,4])
n2=node(2,[5])
n3=node(3,[5,6])
n4=node(4,[2])
n5=node(5,[4])
n6=node(6,[6])

def breadth_first_search(startnode, goalnode):
    queue = Queue()
    queue.append(startnode)

    nodesseen = set()
    nodesseen.add(startnode.id)
    
    #while True:
    while queue:
        node = queue.popleft()
        
        if node is goalnode:
            return True
        else:
            queue.extend(node for node in node.successors if node.id not in nodesseen)
            nodesseen.update(node.successors)
    
    return False

breadth_first_search(n1,n6)
